package puzzle.projecteuler.p200;

import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;
import astudy.util.Combination;


public class Problem111C {

	/**
	 * 简单测算，可以知道
	 * d	M(10,d)
	 * 0	8[1000000007]
	 * 1	9[1111111181]
	 * 2	8[2222222621]
	 * 3	9[3333333323]
	 * 4	9[4444444447]
	 * 5	9[5555555557]
	 * 6	9[6666666661]
	 * 7	9[7777777577]
	 * 8	8[8888888809]
	 * 9	9[9999999929]
	 * 从包含9个d到包含1个d，这样来检测，可以很快的找到M(10,d)
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		long sum = 0;
		for (int d = 0; d < 10; d ++) {
			List<Long> nums = null;
			for (int n = 9; n > -1; n --) {
				nums = get(n, d);
				if (nums.size() > 0) {
					break;
				}
			}
			System.out.println(nums);
			for (Long n: nums) {
				sum += n;
			}
		}
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}
	
	/**
	 * 返回所有包含n的d的10位数
	 * @param d
	 */
	public static List<Long> get(int n, int d) {
		
		List<Long> rs = new ArrayList<Long>();
		//m个位置，存放非d的数字
		int m = 10-n;
		int[] positions = new int[m];
		for (int i = 0; i < positions.length; i ++) {
			positions[i] = i;
		}
		
		while (positions != null) {
			//存放非d的数字的m个位置，分别是数字digits[i]
			int[] digits = new int[m];
			for (int i = 0; i < digits.length; i ++) {
				digits[i] = 0;
			}
			while (digits != null) {
				//get number from positions and digits
				boolean bContainD = false; 
				for (int i = 0; i < digits.length; i ++) {
					if (digits[i] == d) {
						bContainD = true;
					}
				}
				if (!bContainD) {
					int[] ds = new int[] {d,d,d,d,d,d,d,d,d,d};
					for (int i = 0; i < positions.length; i ++) {
						ds[positions[i]] = digits[i];
					}
					long x = 0;
					for (int i = 0; i < ds.length; i ++) {
						x = 10*x + ds[i];
					}
					if (x > 999999999L && AdvMath.isPrime(x)) {
						rs.add(x);
					}
				}
				digits = next(digits);
			}
			//go next loop
			positions = Combination.next(10, positions);
		}
		return rs;
	}
	
	private static int[] next(int[] digits) {
		int j = digits.length-1;
		while (j > -1 && digits[j] == 9) j --;
		if (j < 0) {
			return null;
		}
		digits[j] = digits[j]+1;
		for (int i = j+1; i < digits.length; i ++) digits[i] = 0;
		return digits;
	}
}
